package niuke;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * description:
 * author:zt
 * date:2021-08-09
 */

/**
 * 给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
 * 注意：
 * 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
 * 解集中不能包含重复的三元组。
 */
public class NC54 {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        if (num.length<3) return new ArrayList<>();
        Arrays.sort(num);
        int len = num.length;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            if (i>0 && num[i]==num[i-1]) continue;
            for (int j = i+1; j < len; j++) {
                if (j>i+1 && num[j]==num[j-1]) continue;
                if (num[i]+num[j]>0) break;
                int L = j+1, R = len-1;
                while (L<=R){
                    int mid = (L+R)>>1;
                    if (num[i]+num[j]+num[mid]==0) {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(num[i]);list.add(num[j]);list.add(num[mid]);
                        res.add(list);
                    }
                    else if (num[i]+num[j]+num[mid]>0) R = mid-1;
                    else if (num[i]+num[j]+num[mid]<0) L = mid+1;
                }
            }
        }
        return res;
    }
}
